﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace TreeTraversal
{
    public class BinarySearchTree<T> : BinaryTree<T> where T : IComparable
    {
        public override string Name
        {
            get { return "Binary Search Tree"; }
        }

        protected BinaryTreeNode<T> m_Root = null;

        override public BinaryTreeNode<T> Root()
        {
            return m_Root;
        }

        override public BinaryTreeNode<T> Add(T Value)
        {
            InternalAddResult result = InternalAdd(Value, m_Root);
            return result.Node;
        }

        protected class InternalAddResult
        {
            public BinaryTreeNode<T> Node;
            public bool NewNodeAdded = false;
        }

        protected InternalAddResult InternalAdd(T Value, BinaryTreeNode<T> RootNode)
        {
            if (m_Root == null)
            {
                m_Count++;
                m_Root = new BinaryTreeNode<T>(Value, null);
                InternalAddResult resultTemp = new InternalAddResult();
                resultTemp.NewNodeAdded = true;
                resultTemp.Node = m_Root;
                return resultTemp;
            }

            InternalAddResult result = InternalAddRecursive(Value, m_Root);

            if (result.NewNodeAdded)
            {
                m_Count++;
            }

            return result;
        }

        private InternalAddResult InternalAddRecursive(T Value, BinaryTreeNode<T> RootNode)
        {
            InternalAddResult Result;
            BinaryTreeNode<T> node = null;
            int compare = Value.CompareTo(RootNode.Value);
            if (compare == 0)
            {
                // the item already exists
                // replace value and return this node
                RootNode.Value = Value;

                Result = new InternalAddResult();
                Result.Node = RootNode;
            }
            else if (compare < 0)
            {
                if (RootNode.Left == null)
                {
                    node = new BinaryTreeNode<T>(Value, RootNode);
                    RootNode.Left = node;
                    RootNode.LeftDepth = 1;

                    Result = new InternalAddResult();
                    Result.NewNodeAdded = true;
                    Result.Node = node;
                }
                else
                {
                    Result = InternalAddRecursive(Value, RootNode.Left);
                    if (Result.NewNodeAdded)
                        RootNode.LeftDepth = RootNode.Left.MaxDepth + 1;
                }
            }
            else
            {
                if (RootNode.Right == null)
                {
                    node = new BinaryTreeNode<T>(Value, RootNode);
                    RootNode.Right = node;
                    RootNode.RightDepth = 1;

                    Result = new InternalAddResult();
                    Result.NewNodeAdded = true;
                    Result.Node = node;
                }
                else
                {
                    Result = InternalAddRecursive(Value, RootNode.Right);
                    if (Result.NewNodeAdded)
                        RootNode.RightDepth = RootNode.Right.MaxDepth + 1;
                }
            }

            Debug.Assert(Result != null);
            return Result;
        }

        public BinaryTreeNode<T> Find(T Value)
        {
            return InternalFind(Value, m_Root);
        }

        private BinaryTreeNode<T> InternalFind(T Value, BinaryTreeNode<T> Node)
        {
            if (Node == null)
                return null;

            int compare = Value.CompareTo(Node.Value);
            if (compare == 0)
            {
                return Node;
            }
            else if (compare < 0)
            {
                return InternalFind(Value, Node.Left);
            }
            else
            {
                return InternalFind(Value, Node.Right);
            }
        }
    }
}
